1. Field of the Invention
The present invention relates to data compression/decompression by means of arithmetic coding.
2. Description of the Problem
One technique of compressing and de-compressing data is known as arithmetic coding. A general discussion of arithmetic coding is found in an article by G. Langdon, "An Introduction to Arithmetic Coding", IBM J. Res. Develop. Vol 28, No 2, pages 135-149 (March, 1984), which is incorporated herein by reference.
As discussed in the Langdon article, arithmetic coding maps successively encoded decisions to a code point along a number line. Arithmetic coding may be applied to decisions having two or more possible outcomes (referred to as "events") in which each outcome for a given decision has a probability associated therewith. Each outcome is represented in data by a corresponding "symbol". The number line represents an interval which is partitioned into segments, each segment corresponding to the entering of a respective symbol as input to an encoder. For a decision having four possible outcomes there would be four segments, for example segments a, b, c, and d. The relative length of each segment would reflect the probability of the corresponding event occurring. If the decision corresponds to a "d" event, the "d" segment is selected as a current interval which is then, in turn, partitioned into segments a, b, c, and d. In this way, successively smaller, lesser-included intervals on a number line are derived. Significantly, each interval is arrived at by following a unique sequence of events. The generating of a code stream which points to a particular number line interval in response to a given string of decision events is known as arithmetic coding "encoding".
From a particular interval and information regarding the ordering and respective lengths of the segments of each interval, an associated string of decision events can be retrieved. This process, which undoes the arithmetic coding encoding, is labelled as arithmetic coding "decoding".
Binary arithmetic coding is a special case in which each decision results in one of two exclusive events. In the binary coding environment, one of the two events involves a less probable symbol (LPS) which has a probability of Q and the second event involves a more probable symbol (MPS) which has a probability of P. In binary arithmetic coding, an interval along the number line is divided into two segments--one corresponding to the occurrence of an LPS event (or outcome) and the other segment corresponding to the occurrence of an MPS event (or outcome). The length of each segment preferably reflects the probabilities Q and P, respectively, of the two events.
In a binary arithmetic encoder, a number line extends between 0 and 1 to define an initial interval. In a hardware scheme described in the Langdon article, a first segment extending along the lower values of the interval corresponds to the LPS probability. A second segment, extending along the higher values of the interval, corresponds to the MPS probability. A code point is initially set to point at the low end of the interval (that is, at 0) and a code stream corresponding thereto is also initialized at 000 . . . It is important to note that although the number line extends from 0-to-1, only one of the two boundary values is included in the corresponding interval. For example, the initial hardware interval includes the 0 and all points up to but not including 1. Similarly, for each successive interval in the hardware scheme, the lower bound is included but the upper bound is not.
For the above-discussed hardware scheme, in the event of an LPS, the code point remains fixed and the code stream remains the same in value (although its length increases). A new current interval after an LPS event is defined as the LPS (or Q) segment of the predecessor interval. Also for the abovediscussed hardware scheme, in the event that an MPS occurs with the 0-to-1 bounds in place, the code point increments by the value of Q and the new current interval becomes that associated with the MPS event, i.e. the P segment of the previous interval. It has been observed for hardware encoders that movement of the code point on each MPS event is far superior to movement on LPS events.
In a novel software approach to encoding (disclosed herein), the upper bound may be included in the interval but the lower bound is not. That is, for the number line extending from 0-to-1, the interval includes 1 and all points extending down to but not including 0. According to this software scheme, the value of the code stream has a value corresponding to the upper bound of the current interval and is decremented with each LPS event. It has been found by the present inventors that moving the code stream on LPS events in a software scheme is more efficient than movement on MPS events.
In some instances it is desired or necessary to determine (or encode) the code point value in hardware while in other instances the code point value is preferably encoded with software. Similarly, in retrieving the original decision data from a given code stream (indicative of a corresponding code point in an interval), a hardware decoder may be appropriate or required in some instances whereas a software decoder may be appropriate or required in other instances. Hence, it would be highly desirable for a hardware encoder and a software encoder to generate the same code stream or at least code streams pointing to the same interval for a given set of decisions, and for a hardware decoder and a software decoder to retrieve the same set of decision data given such code streams. In this way, data could be encoded by means of hardware or software to generate a code stream, and the code stream could be decoded by software or hardware to recover the initial data.
To date, however, it has not been suggested that code streams generated by optimized hardware and optimized software might be interchangeable. Observing the respective conventions outlined above for the discussed hardware and software schemes, it is noted that the hardware code stream and software code stream do not point to the same code point on the number line. (In the initial condition, for example, the hardware code stream points to while the software code stream points to 1.) By pointing to different code points, the code streams are not identical. Furthermore, the two code streams--as suggested hereinabove--do not point to the same interval along the number line. By pointing to different intervals, the code streams are not even compatible, i.e., decodable by the same decoder. In this regard, it is observed that a decoder can retrieve the same set of decision events from various code points in a given interval. Hence, two encoders which encode different code points in the same final interval will be decoded to produce the same original decision data. Two encoders that produce code streams that do not point to the same final interval are not compatible.
The above-described compatibility problem is compounded because encoding is performed with "finite precision". With finite precision, the code stream increases in length without any prescribed limit as each decision event is encoded; however, only a finite portion of the code stream is retained in storage. That is, the code stream is stored in a shift register or other fixed length memory. As an event is encoded, new contents enter the code stream memory. At some time, earlier stored contents of the memory are "shipped out" from the fixed length memory. The contents which are shipped out can no longer be altered.
The fact that the shipped out contents cannot be altered can lead to difficulties. The first difficulty is called "carry propagation". In an encoding scheme in which the code stream either remains constant or is incremented--as in the aforementioned hardware scheme--there is a possibility that the current code stream C may be of the form 011111111111. If the fixed length memory stores only the least significant eight bits and the value of C is incremented by, for example, 0000000001, the new value for C should be 1000[00000000]. If the left four bits have already been shipped out and cannot be altered, there is a discrepancy; the bits as shipped were 0111 whereas the actual value--after carry propagation--should be 1000. If only the least significant (bracketed) 8 bits are retained, the carry cannot reach its destination. The carry propagation difficulty has been recognized in the prior art. In the IBM Journal of Research and Development, 28, 135, (1984), G. G. Langdon, Jr. describes the general concept of bit stuffing to block carry propagation--such bit stuffing being unlinked to data bytes.
A second difficulty attaching to finite precision involves those arithmetic coding encoders in which the upper bound is contained within the interval and in which code point movement is achieved by subtracting a value from the current code stream. Such a scheme is suggested by the aforementioned software encoder. Therein, the current code stream C points to the upper bound of an interval. In response to an LPS event, the P interval is subtracted from C to yield a new value for the code stream. (See FIG. 4) If the code stream includes a string of 0 bits after a 1 (e.g., 1000000000000) and there is finite precision, the leading bits which include the 1 bit may have already been shipped out so that a future borrow could not be accounted for. In the above example, for an 8-bit register, the leading bits 10000 would have already been shipped and would no longer be subject to change. A subtraction of 00000001 from the eight 0's stored in the shift register or other memory results in a borrow propagation which is unable to reach a 1 bit whereat a borrow may be effected. Such borrow propagation presents a notable difficulty resulting from finite precision processing.
In addition to creating difficulties within a given encoder, the discrepancies resulting from finite precision processing have hampered compatibility between encoders. That is, the discrepancies have made it difficult to obtain the same or a compatible code stream for (a) an encoder that involves incrementing the code stream value in response to a prescribed event and (b) an encoder that involves decrementing the code stream value in response to a prescribed event.
The problem of generating an identical or at least a compatible code stream with an incrementing encoder and with a decrementing encoder is highlighted when one considers the optimal conventions ascribed to a hardware encoder and to a software encoder.
For optimal operation, the hardware encoder moves the code point on an MPS event which, in a convenient embodiment, results in an incrementation in code stream value. Optimal operation for the software scheme involves moving the code point on an LPS event and, in a convenient embodiment, results in decrementing the code stream value. To make the two code streams decodable by a single decoder, the finite precision difficulties as well as the disparity in pointing of the respective code streams must be resolved.
At this time, it is noted that the present inventors have alternatively proposed that the probability segments of an interval may be "inverted". For example, instead of having the P segment at the high (in value) end of an interval, the P segment may occupy the lower end of the interval. A shorthand notation for the former convention is "P/Q" whereas the latter convention is "Q/P". An example of an inverted Q/P encoder would point the current code stream at the lower boundary of an interval (which point is included in the interval). The Q segment is at the high end of the current interval and the P segment occupies the lower end of the interval. For an inverted software encoder, in the event of an MPS, the code point is unmoved. On each LPS event, the Q/P inverted software encoder increments the value of C by the P segment value starting from the lower boundary of the current interval. The inverted software encoder operates as a mirror image of the above-described P/Q software encoder. It is noted that the Q/P inverted software encoder value for the code stream C.sub.I is related to the P/Q software encoder value C.sub.s by the expression: C.sub.I =1-C.sub.s. Because the length of C.sub.s is not fixed, the value of 1 is indeterminate in length. Again, borrow propagation difficulties may result in attempting to employ the inverted code encoder to generate a code stream compatible or identical with a code stream generated by an optimal P/Q hardware or an optimal P/Q software encoder.
A number of problems preclude an optimal hardware encoder and an optimal software encoder (whether following P/Q or Q/P symbol ordering) from being interchangeable--from producing the same or at least compatible code streams. Similarly, there are a number of problems precluding the interchangeable use of an optimal software decoder and an optimal hardware decoder in retrieving an original set of decision events from a code stream generated by an optimal hardware encoder or an optimal software encoder. The present invention involves configuring the various software and hardware encoders to be interchangeable and for either an optimal hardware decoder or an optimal software decoder to similarly decode a code stream from any of the interchangeable encoders.